// https://soj.turingedu.cn/problem/60202/
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
int rad(); // read int
const int max_size = 5 + 100;
const int maxn = 5 + 1e6;

int n;
int a[maxn];
int tag[maxn << 2];

struct Node {
    ll sum, pre, suf, val;
} tr[maxn << 2];

// ll sum[maxn << 2]; // sum[now] = sum[l] + sum[r]
// ll pre[maxn << 2]; // pre[now] = max{pre[l], sum[l] + pre[r]}
// ll suf[maxn << 2]; // suf[now] = max{suf[l] + sum[r], suf[r]}
// ll val[maxn << 2]; // val[now] = max{val[l], val[r], suf[l] + pre[r]}

Node merge(const Node &l, const Node &r) { // merge the subtree
    return {l.sum + r.sum,
            max(l.pre, l.sum + r.pre),
            max(l.suf + r.sum, r.suf),
            max(max(l.val, r.val), l.suf + r.pre)};
}

// inline void update_node(int now, int l, int r, ll x) { // update the node by tag
//     sum[now] += x * (r - l + 1);
//     tag[now] += x;
// }
// inline void push_down(int now, int l, int r) { // update the subnode and push down the tag
//     if (tag[now] == 0) return;
//     int mid = l + r >> 1;
//     update_node(now << 1, l, mid, tag[now]);
//     update_node(now << 1 | 1, mid + 1, r, tag[now]);
//     tag[now] = 0;
// }

void init(int now, int l, int r) { // init the tree
    if (l == r) {
        tr[now] = {a[l], a[l], a[l], a[l]};
        return;
    }
    int mid = l + r >> 1;
    init(now << 1, l, mid);
    init(now << 1 | 1, mid + 1, r);
    tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
}

void update(int now, int l, int r, int i, ll x) {
    if (l == r) {
        tr[now] = {x, x, x, x};
        return;
    }
    int mid = l + r >> 1;
    if (i <= mid)
        update(now << 1, l, mid, i, x);
    else
        update(now << 1 | 1, mid + 1, r, i, x);
    tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
}
// void update(int now, int l, int r, int s, int t, ll x) { // update the [s, t] by tag
//     if (s <= l && r <= t) {
//         update_node(now, l, r, x);
//         return;
//     }
//     push_down(now, l, r);
//     int mid = l + r >> 1;
//     if (s <= mid) update(now << 1, l, mid, s, t, x);
//     if (t > mid) update(now << 1 | 1, mid + 1, r, s, t, x);
//     merge(now);
// }

Node ask(int now, int l, int r, int s, int t) { // ask the [s, t]
    if (s <= l && r <= t) return tr[now];       // cover
    // push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask(now << 1, l, mid, s, t);
    if (s > mid) return ask(now << 1 | 1, mid + 1, r, s, t);
    return merge(ask(now << 1, l, mid, s, t), ask(now << 1 | 1, mid + 1, r, s, t));
}

int main() {
    n = rad();
    int q = rad();
    rf(i, n) a[i] = rad();
    init(1, 1, n);
    rf(j, q) {
        int op = rad();
        if (op == 2) {
            int i = rad(), x = rad();
            update(1, 1, n, i, x);
        } else if (op == 1) {
            int l = rad(), r = rad();
            if (l > r) swap(l, r);
            printf("%lld\n", ask(1, 1, n, l, r).val);
        }
    }
}

int rad() {
    int back = 0, ch = 0, neg = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        neg = ch == '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return (back ^ -neg) + neg;
}